package Ep06_BinaryTree.BT25_0501;

import Ep06_BinaryTree.TreeNode;

import java.util.ArrayList;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/6/24 18:26
 * 说明：leetcode 501
 *      找众数，依然是双指针
 */

public class Mine {
    TreeNode pre = null;
    int count = 0;
    int maxCount = 0;
    ArrayList<Integer> result = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        traversal(root);
        // 由 ArrayList<Integer> 转为 int[] 的方法
        // 可以 ArrayList.stream.mapToInt(Integer::valueOf).toArray(); 这样处理需要绕一大个弯
        // 相比之下，循环赋值这种方法会很快
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void traversal(TreeNode cur) {
        if (cur == null) return;
        // 左
        traversal(cur.left);
        // 中
        if (pre == null) {
            count = 1;
        } else if (cur.val == pre.val) {
            count++;
        } else {
            count = 1;
        }
        pre = cur;  // 将pre指针向下一个节点移动一位
        if (count == maxCount) {
            result.add(cur.val);
        }
        if (count > maxCount) {
            maxCount = count;
            result.clear();
            result.add(cur.val);
        }
        // 右
        traversal(cur.right);
    }
}
